优化算法在机器学习中扮演着至关重要的角色,了解常用的优化算法对于机器学习爱好者和从业者有着重要的意义。

这系列文章先讲述优化算法和机器学习的关系,然后罗列优化算法分类,尤其是机器学习中常用的几类.接下来明确下数学符号,开始按照历史和逻辑顺序,依次介绍各种机器学习中常用的优化算法.

这篇先讲其中基于一阶导数的标准梯度下降法和Momentum,其中穿插学习率退火方法和基于二阶导数的优化算法来辅助说明各算法的意义和背后的想法.

优化算法和机器学习的关系

机器学习的过程往往是

• 建模实际问题,定义损失函数
• 代入训练数据,利用优化算法来优化损失函数并更新参数,直到终止条件(比如迭代数或者更新的收益或者损失函数的大小) 可见优化算法和损失函数在机器学习中占有重要的地位.

优化算法分类

优化算法有很多种,常见的包括

• 基于导数的,比如基于一阶导数的梯度下降法(GD, Grandient Descent)和基于二阶导数的牛顿法等,要求损失函数(运筹学中更多叫做目标函数)可导
• 群体方法(population method),比如遗传算法(Genetic Algo)和蚁群算法(Ant Colony Optimization),不依赖于问题(problem-independent),不需要对目标函数结构有太多的了解
• 单体方法(single-state method),比如模拟退火算法(Simulated Annealing),同样,不依赖于问题(problem-independent),不需要对目标函数结构有太多的了解 等.

机器学习中常用的是基于导数,尤其是基于一阶导数的优化算法,包括

• 标准梯度下降法(GD, standard Gradient Descent)
• 带有momentum的GD
• RMSProp (Root Mean Square Propagation)
• AdaM (Adaptive Moment estimates)
• AdaGrad (Adaptive Gradient Algo)
• AdaDelta

符号规定

在具体解释前先规定下符号

• 损失函数为 $L(x)$ （很多地方也会写作$ J(x)$ ）
• 梯度为 $ g(x) = \frac{\partial L(x)}{\partial x} $
• $g_t$ 表示第t次迭代的梯度,
• 第t次迭代时, $x_{t+1} = x_t + \Delta x_t $
• 学习率为 $\eta $
• $o(f(x))$ 表示 $f(x)$ 的高阶无穷小,也就是当 $f(x) $无限接近0时, $g(x) = o(f(x)), \lim_{f(x)\to0} \frac{g(x)}{f(x)} = 0 $,比如 $x^2$ 就是 $x$的高阶无穷小

标准梯度下降法(GD, standard Gradient Descent)

每次迭代的更新为 $\Delta x_t = - \eta* g_t $

标准GD的想法来源于一阶泰勒展开 $f(x_1) = f(x_0) + f'(x)|_{x=x_0} * (x_1 - x_0) + o(x_1-x_0) $.

其中 $o(x_1-x_0)$ 叫做皮亚诺(Peano)余项,当 $x_1 - x_0$ 很小时,这个余项可以忽略不计.
当 $x_1 - x_0$ 和一阶导数也就是梯度相反方向时, 损失函数下降最快.

一个经典的解释是:想象我们从山上下来,每步都沿着坡度最陡的方向.这时,水平面是我们的定义域,海拔是值域.

GD缺点

但GD有两个主要的缺点:

• 优化过程中,保持一定的学习率,并且这个学习率是人工设定.当学习率过大时,可能在靠近最优点附近震荡(想象一步子太大跨过去了);学习率过小时,优化的速度太慢
• 学习率对于每个维度都一样,而我们经常会遇到不同维度的曲率(二阶导数)差别比较大的情况,这时GD容易出现zig-zag路径.(参考图2,优化路径呈现zig-zag形状,该图绘制代码放在附录1中)

考虑

所以人们考虑

• 动态选择更好的学习率,比如前期大些来加速优化,靠近低点了小些避免在低点附近来回震荡,甚至
• 为每个维度选择合适的学习率 $\eta$ .

学习率退火 (Learning Rate Annealing)

出于考虑1,人们参考了单体优化方法中的模拟退火(Simulated Annealing),学习率随着迭代次数的增加或者损失函数在验证集上的表现变好而衰减(decay). 学习率退化可以直接加在GD上.

改进方向

AdaGrad等算法(我的一篇知乎文章有介绍)就借鉴了退火的学习率衰减的思想.不过这个不是这篇的重点.

牛顿法 (Newton's Method)

出于考虑2(为每个维度选择合适的$\eta$),基于二阶导数的牛顿法被提出.它来源于泰勒二阶展开.
$f(x_1) = f(x_0) + f'(x)|_{x=x_0} * (x_1 - x_0) + \frac{(x_1-x_0)^2}{2!} f''(x)|_{x={x_0}} + o((x_1-x_0)^2) $.

对于多元函数 x ,
$f(x_1) = f(x_0) + g(x_0) * (x_1 - x_0) + \frac{1}{2!} (x_1-x_0) H(x_0) (x_1-x_0)^t+ o((x_1-x_0)^2) $

其中 $H(x)$ 为Hessian矩阵 有 $H[i, j] = \frac{\partial^2{L}}{\partial{x^i}\partial{x^j}}$ .

这样每次迭代都会考虑损失函数的曲率(二阶导数)来选择步长.对比上图中的标准GD,牛顿法可以一步就到达最优点.

牛顿法缺点

但是牛顿法的计算复杂度很高,因为Hessian矩阵的维度是参数个数的平方,而参数的个数往往很多.

改进方向

不同的方法随即被提出,比如

• Becker和LeCun提出的用对角线元素来代替Hessian全矩阵

• 依靠历史的梯度信息来模拟二阶方法,包括Momentum,RMSProp(用二阶距来模拟二阶导数),AdaM(用一阶矩和二阶矩的比例来模拟二阶导数)等.

我们先介绍Momentum

Momentum

借鉴了物理中动量(momentum)的概念,让 $\Delta x_t $保留一部分之前的方向,而不是完全用梯度的负方向.

每次迭代的更新为 $\Delta x_t = - \eta* g_t + \rho * \Delta x_{t-1} $
或
$\Delta x_t = \eta * （\mu * \Delta x_{t-1} - g_t) $
其中$\mu$也可以写成momentum

这样预期可以达到两个效果:

• 某个维度在近几次迭代中正负号总是改变时,说明二阶导数可能相对其他维度比较大或者说每次步子迈得太大了,需要改变幅度小些或者迈得小点来避免zig-zag路径
• 某个维度在近几次迭代中符号几乎不变,说明二阶导数可能相对其他维度比较小或者说大方向是正确的,这个维度改变的幅度可以扩大些,来加速改进.

如下图所示,加入了Momentum,前期的训练加快了,靠近低点时也减小了震荡.